import sun.reflect.generics.tree.Tree;

import java.util.TreeSet;

public class project {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int len=nums.length;
        TreeSet<Long> ts=new TreeSet<>();
        for(int i=0;i<len;i++){
            Long u=nums[i]*1L;
            Long l=ts.floor(u);
            Long r=ts.ceiling(u);
            if(l!=null&&u-l<=t){
                return true;
            }
            if(r!=null&&r-u<=t){
                return true;
            }
            ts.add(u);
            if(i>=k){
                ts.remove(nums[i-k]*1L);
            }
        }
        return false;
    }
















    public boolean containsNearbyAlmostDuplicate1(int[] nums, int k, int t) {
        int len=nums.length;
        TreeSet<Long> ts=new TreeSet<>();
        for(int i=0;i<nums.length;i++){
            Long u=nums[i]*1L;
            Long l=ts.floor(u);
            Long r=ts.ceiling(u);
            if(l!=null&&u-l<=t){
                return true;
            }
            if(r!=null&&r-u<=t){
                return true;
            }
            ts.add(u);
            if(i>=k){
                ts.remove(nums[i-k]*1L);
            }
        }
        return false;
    }














    public int combinationSum4(int[] nums, int target) {
        int[] dp=new int[target+1];
        dp[0]=1;
        for(int i=1;i<=target;i++){
            for(int j : nums){
                if(j<=i){
                    dp[i]+=dp[i-j];
                }
            }
        }
        return dp[target];
    }











    public int combinationSum1(int[] nums, int target) {
        int[] arr=new int[target+1];
        arr[0]=1;
        for(int i=1;i<=target;i++){
            for(int j : nums){
                if(j<=i){
                    arr[i]+=arr[i-j];
                }
            }
        }
        return arr[target-1];
    }











    public int dayOfYear(String date) {
        int[] arr={31,28,31,30,31,30,31,31,30,31,30,31};
        int year=Integer.parseInt(date.substring(0,4));
        int month=Integer.parseInt(date.substring(5,7));
        int day=Integer.parseInt(date.substring(8));
        if(year%4==0&&year%100!=0||year%400==0){
            arr[1]++;
        }
        int sum=0;
        for(int i=0;i<month;i++){
            sum+=arr[i];
        }
        return sum+day;
    }
}
